package com.example.Arithmetic.Arithmetic;

import java.util.Arrays;

/**
 * 日期：2023/12/21
 * 时间：11:44
 * 描述：B树实现
 */
public class BTree {

    private class Node {
        int[] keys;  //关键字
        Node[] children; //孩子数
        int keyNumber;  //有效关键字数目
        boolean leaf = true; //是否叶子节点，默认为teur
        int t;  //最小度数

        public Node(int t) {   //d>=2
            this.t = t;
            this.children = new Node[t * 2];     //可能拥有最多的孩子数
            this.keys = new int[t * 2 - 1];
        }

        @Override
        public String toString() {
            return Arrays.toString(Arrays.copyOfRange(keys, 0, keyNumber));
        }

        /**
         * 获取指定key
         *
         * @param key
         * @return
         */
        public Node get(int key) {
            int i = 0;
            while (i < keyNumber) {
                if (key == keys[i]) {
                    return this;
                }
                if (key < keys[i]) {
                    break;
                }
                i++;
            }
            //是叶子节点直接退出，没有可找的
            if (leaf) {
                return null;
            }
//            递归调用，从孩子节点中继续查找
            return children[i].get(key);
        }

        /**
         * 向指定位置插入索引
         *
         * @param key
         * @param index
         */
        public void insertKey(int key, int index) {
            System.arraycopy(keys, index, keys, index + 1, keyNumber - index);
            keys[index] = key;
            keyNumber++;
        }

        /**
         * 向孩子指定索引处插入孩子
         *
         * @param child
         * @param index
         */
        public void insertChild(Node child, int index) {
            System.arraycopy(children, index, children, index + 1, keyNumber - index);
            children[index] = child;
        }

        //移除指定索引处的key
        int removeKey(int index) {
            int t = keys[index];
            System.arraycopy(keys, index + 1, keys, index, keyNumber - index);
            return t;
        }

        //移除最左边key
        int removeLeftKey() {
            return removeKey(0);
        }

        //移除最右边key
        int removeRightKey() {
            return removeKey(keyNumber - 1);
        }

        //移除指定index位置的child
        Node removeChild(int index) {
            Node t = children[index];
            System.arraycopy(children, index + 1, children, index, keyNumber - index);
            children[keyNumber] = null;
            return t;
        }

        //移除最左边key
        Node removeLeftChild() {
            return removeChild(0);
        }

        //移除最右边key
        Node removeRightChild() {
            return removeChild(keyNumber);
        }

        //找到index孩子处左边兄弟
        Node childLeftSibling(int index) {
            return index > 0 ? children[index - 1] : null;
        }

        //找到index孩子处右边兄弟
        Node childRightSibling(int index) {
            return index == keyNumber ? null : children[index + 1];
        }

        //复制当前节点所有key和child到target
        void moveToTarget(Node target) {
            int start = target.keyNumber;
            if (!leaf) {
                for (int i = 0; i <= keyNumber; i++) {
                    target.children[start + i] = children[i];
                }
            }
            for (int i = 0; i < keyNumber; i++) {
                target.keys[target.keyNumber++] = keys[i];
            }
        }
    }

    Node root;
    int t;
    final int MAX_KEY_NUMBER;
    final int MIN_KEY_NUMBER;

    public BTree() {
        this(2);
    }

    public BTree(int t) {
        this.t = t;
        this.root = new Node(t);
        MAX_KEY_NUMBER = t * 2 - 1;
        MIN_KEY_NUMBER = t - 1;
    }


    /**
     * 判断树中是否存在key
     *
     * @param key
     * @return
     */
    public boolean containsKey(int key) {
        return root.get(key) != null;
    }

    /**
     * 添加方法，递归调用
     *
     * @param key
     */
    public void put(int key) {
        doPut(root, key, null, 0);
    }

    private void doPut(Node node, int key, Node parent, int index) {
        int i = 0;
        while (i < node.keyNumber) {
            if (key == node.keys[i]) {
                return;   //走更新逻辑
            }
            if (key < node.keys[i]) {
                break;
            }
            i++;
        }
        if (node.leaf) {
            node.insertKey(key, i);
        } else {
            doPut(node.children[i], key, node, i);
        }
//        插入完判断是否到达上限，到达就分裂，还要判断父节点分裂后是否到达了上限
        if (node.keyNumber == MAX_KEY_NUMBER) {
            split(parent, node, index);
        }
    }

    /**
     * 分裂方法
     *
     * @param parent
     * @param left
     * @param index
     */
    private void split(Node parent, Node left, int index) {
//        根节点分裂的情况
        if (parent == null) {
            Node newRoot = new Node(t);
            newRoot.leaf = false;
            newRoot.insertChild(left, 0);
            root = newRoot;
            parent = newRoot;
        }
//        先创建右节点，分走t索引后面的部分
        Node right = new Node(t);
//        右节点是否为叶子节点取决于左叶子节点是否是叶子节点
        right.leaf = left.leaf;
        System.arraycopy(left.keys, t, right.keys, 0, t - 1);
//        非叶子节点，需要把孩子移动
        if (!left.leaf) {
            System.arraycopy(left.children, t, right.children, 0, t);
        }
        right.keyNumber = left.keyNumber = t - 1;
//        分走中间节点
        parent.insertKey(left.keys[t - 1], index);
//        调整父节点孩子位置
        parent.insertChild(right, index + 1);
    }

    /**
     * 删除指定key
     * case1:当前节点是叶子节点，没找到
     * case2:当前节点是叶子节点，找到了
     * case3:当前节点是非叶子节点，没找到
     * case4:当前节点是非叶子节点，找到了
     * case5：删除后key数目<下限（不平衡）
     * case6：根节点（需要更细致调整）
     *
     * @param key
     */
    public void remove(int key) {
        doRemove(null, root, 0, key);
    }

    public void doRemove(Node parent, Node node, int index, int key) {
        int i = 0;
        while (i < node.keyNumber) {
            if (node.keys[i] >= key) {
                break;
            }
            i++;
        }
        //两种情况
//        找到，i代表被删除key索引
//        没找到，代表继续从第i索引孩子处找
//        是叶子节点
        if (node.leaf) {
            if (found(node, key, i)) {//case1
                return;
            } else {  //case2
                node.removeKey(i);
            }
//            不是叶子节点
        } else {
            if (found(node, key, i)) {//case3
                doRemove(node, node.children[i], i, key);
            } else {  //case4
//                找到后继key
                Node s = node.children[i + 1];
                while (!s.leaf) {
                    s = s.children[0];
                }
//                李代桃僵
                int skey = s.keys[0];
                node.keys[i] = skey;
                doRemove(node, node.children[i + 1], i + 1, key);
            }
        }
//        调整平衡，case5和6
        if (node.keyNumber < MIN_KEY_NUMBER) {
            balance(parent, node, index);
        }
    }

    private void balance(Node parent, Node node, int index) {
//        case6
        if (node == root) {
            if (root.keyNumber == 0 && root.children[0] != null) {
                root = root.children[0];
            }
            return;
        }
        Node left = parent.childLeftSibling(index);
        Node right = parent.childRightSibling(index);
//       5.1左边富余，右旋
        if (left != null && left.keyNumber > MIN_KEY_NUMBER) {
//            把父节点key换下来
            node.insertKey(parent.keys[index - 1], 0);
//           非叶子节点 孩子有多余的
            if (!left.leaf) {
//                给左边最大孩子换个爹
                node.insertChild(left.removeRightChild(), 0);
            }
//            左节点值换给父节点
            parent.keys[index - 1] = left.removeRightKey();
            return;
        }
//       5.2右边富余，左旋
        if (right != null && right.keyNumber > MIN_KEY_NUMBER) {
//            把父节点key换下来
            node.insertKey(parent.keys[index], node.keyNumber);
//           非叶子节点 孩子有多余的
            if (!left.leaf) {
//                给右边最大孩子换个爹，换给左边最右边
                node.insertChild(right.removeLeftChild(), node.keyNumber + 1);
            }
//            右节点值换给父节点
            parent.keys[index] = right.removeLeftKey();
            return;
        }
//       5.3两边都不够，合并
//        有左兄弟的情况
        if (left != null) {
//            向左兄弟合并
            parent.removeChild(index);
            left.insertKey(parent.removeKey(index - 1), left.keyNumber);
            node.moveToTarget(left);
        } else {
//            向自己合并
            parent.removeChild(index + 1);
            node.insertKey(parent.removeKey(index), node.keyNumber);
            right.moveToTarget(node);
        }
    }

    private static boolean found(Node node, int key, int i) {
        return i >= node.keyNumber || (i < node.keyNumber && node.keys[i] != key);
    }

    public static void main(String[] args) {
        BTree bTree = new BTree(3);
        for (int i = 1; i <= 100; i++) {
            bTree.put(i);
        }
        bTree.remove(54);
        System.out.println("root:" + bTree.root.toString());
        for (int i = 0; i < bTree.root.children.length; i++) {
            if (bTree.root.children[i] != null) {
                System.out.println("第二层root.children,index=" + i + ":" + bTree.root.children[i].toString());
                for (int j = 0; j < bTree.root.children[i].children.length; j++) {
                    if (bTree.root.children[i].children[j] != null) {
                        System.out.println("第三层root.children.children,index=" + j + ":" + bTree.root.children[i].children[j].toString());
                        for (int k = 0; k < bTree.root.children[i].children[j].children.length; k++) {
                            if (bTree.root.children[i].children[j].children[k] != null) {
                                System.out.println("第四层root.children.children,index=" + k + ":" + bTree.root.children[i].children[j].children[k].toString());
                            }
                        }
                    }
                }
            }
        }
    }
}

